#include <iostream>
using namespace std;

int MinInOrder(int data[], int index1, int index2)
{
    int result = data[index1];
    for(int idx = index1 + 1; idx <= index2; ++ idx)
        if (result > data[idx])
            result = data[idx];
    return result;
}

int MinNumberOfRotatedArray(int data[], int length)
{
    if (data == NULL || length <= 0)
    {
        cout << "Invalid Input" << endl;
        return 0;
    }
    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;
    // 循环的条件
    while (data[index1] >= data[index2])
    {
        if(index2 - index1 == 1)
        {
            indexMid = index2;
            break;
        }
        indexMid = (index1 + index2) / 2;

        // 如果下标index1, index2和indexMid指向的三个数字相同，则只能顺序查找
        if(data[index1] == data[index2] && data[indexMid] == data[index1])
            return MinInOrder(data, index1, index2);

        if (data[indexMid] >= data[index1])
            index1 = indexMid;
        else if(data[indexMid] <= data[index2])
            index2 = indexMid;
    }
    return data[indexMid];
}

int main(int argc, char * argv[])
{
    int data[] = {3, 3, 0, 3, 3, 3, 3};
    int length = sizeof(data) / sizeof(int);
    int minVal = MinNumberOfRotatedArray(data, length);
    cout << minVal << endl;
    return 0;
}
